//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
//
//
//
// 示例 1:
//
//
//输入: s = "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//
//
// 示例 2:
//
//
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//
//
// 示例 3:
//
//
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 5 * 10⁴
// s 由英文字母、数字、符号和空格组成
//
// Related Topics 哈希表 字符串 滑动窗口 👍 7736 👎 0

package leetcode.editor.cn;

class 无重复字符的最长子串 {
    public static void main(String[] args) {
        Solution solution = new 无重复字符的最长子串().new Solution();
        int length = solution.lengthOfLongestSubstring("bbcdefghijklmnopqrsta");
        System.out.println(length);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0 || s.equals("")) {
                return 0;
            }
            char[] str = s.toCharArray();
            int[] map = new int[256];//ascii码 上次出现的位置  new int[26]  map[str[i]-'a']
            for (int i = 0; i < 256; i++) {
                map[i] = -1;//初始化表示没出现过
            }
            map[str[0]] = 0;//第0位的字母在map中的相应位置首次出现在0
            int N = str.length;
            int ans = 1;//最长子串最少为1
            int pre = 1;
            for (int i = 1; i < N; i++) {
                pre = Math.min(i - map[str[i]], pre + 1);
                ans = Math.max(ans, pre);
                map[str[i]] = i;//这个不能拿出来单独初始化   外侧初始化会导致第一次出现的位置不准
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
